package example2;

//200. 岛屿数量
public class LeetCode200 {
    public static void main(String[] args) {
        char[][] grid1 = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        char[][] grid2 = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        char[][] grid3 = {
                {'1', '1', '1'},
                {'0', '1', '0'},
                {'1', '1', '1'}
        };
        System.out.println(new Solution200().numIslands(grid3));
    }
}

/**
 * 方法一：自己想的深度优先搜索方法。同样过度优先用队列也可以。还可以通过并查集的方式，但也会判断每个节点四周的节点
 */
class Solution200 {
    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int num = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j] == '1'){
                    num++;
                    check(grid,i,j);
                }
            }
        }
        return num;
    }

    public void check(char[][] grid,int x,int y){
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length)    return;
        if(grid[x][y] == '0' || grid[x][y] == '2')   return;
        if(grid[x][y] == '1'){
            grid[x][y] = '2';
        }
        check(grid,x-1,y);
        check(grid,x,y-1);
        check(grid,x,y+1);
        check(grid,x+1,y);
    }
}
